HPAVC/HPAVC CD-ROM.iso/pc/ARASAN_S.ZIP/SEARCH.CPP

C/C++ Source or Header | 1994-08-14 | 36.1 KB | 1,350 lines

// Copyright 1994 by Jon Dart.  All Rights Reserved.

#include "bearing.h"
#include "search.h"
#include "scoring.h"
#include "constant.h"
#include "movegen.h"
#include "moveord.h"
#include "util.h"
#include "rmove.h"
#include "pinfo.h"
#include "attacke.h"
#ifdef WINDOWS
#include "clock.h"
#include "display.h"
#endif
#include "options.h"
#include "globals.h"
#ifdef WINDOWS
#include <wpapp.h>
#define SEARCH_TIMER 2
#else
#include <stdio.h>
#define wsprintf sprintf
#endif
#ifdef TRACE
#include <iostream.h>
#endif
#include <limits.h>

#if defined(__BORLANDC__) && !defined(WINDOWS)
// expand default stack size
extern unsigned _stklen = 0x8000;
#endif
extern Options *global_options;

// Define the allocators for the hash table here:
Pool S_Node<Position_Info>::allocator(4096);
Pool S_List<Position_Info>::allocator(4096);

#ifdef WINDOWS
// We have a limited ability to perform multiple searches at once.
// E.g. the "hint" function uses this.  Each search gets its own
// timer.
#define MAX_SEARCHES 3
static int num_searches = 0;
static Search *searches[MAX_SEARCHES];
HACCEL Search::accel = 0;
#endif

static unsigned pred_moves = 0;
static unsigned moves_in_game = 0;

const int Illegal = Constants::BIG + 1000;

#ifdef TRACE
static void indent(const int ply)
{
   for (int k = 0; k < ply; k++) cout << ' ';
}
#endif

#ifdef USE_HASH
// To reduce the chance of a hash collision, we do some elementary
// testing on moves returned by the hash table, to help weed out
// any that are invalid in the current board position ..
static Boolean hash_move_valid( const Board &board, const Move &move)
{
    if (move.IsNull())
        return True;
    Piece p = board[move.StartSquare()];
    if (!p.IsEmpty() && p.Color() == board.Side())
    {
      p = board[move.DestSquare()];
    return (p.IsEmpty() || p.Color() != board.Side());
    }
    else
        return False;
}
#endif

struct Extensions
{
    enum { Capture_Depth = 4 };
    enum { Check_Depth = 2 };
    enum { Max_Extension = 4};
};

Search::Statistics::Statistics()
{
   clear();
}

void Search::Statistics::clear()
{
   state = Normal;
   value = 0;
   for (int i = 0; i < Constants::MaxPly; i++)
       best_line[i].MakeNull();
   elapsed_time = 0;
   plies_completed = max_depth = 0;
   num_moves = num_pos = 0;
}

int Search::get_ply() const
{
     return display_depth;
}

unsigned long Search::get_numpos() const
{
     return num_pos;
}

void Search::terminate_now()
{
    time_up = True; terminated = True;
}

#ifdef WINDOWS
void FAR PASCAL _export TimerProc( HWND hWnd, UINT /*msg*/, UINT wParam,
DWORD /*lParam*/)
{
    // timer callback function
    time_t current_time = time(NULL);
    Search *searcher = searches[wParam-SEARCH_TIMER];
    if (searcher->was_terminated())
        return;
    const Search_Type src_type = searcher->get_search_type();
    if (src_type != Fixed_Ply &&
       current_time - searcher->get_start_time() > searcher->get_time_limit())
       searcher->set_time_up(True);
    the_clock->update( );
//    if (src_type != Fixed_Ply && src_type != Time_Limit)
//    {
//       // check if we've exceeded the time control
//       if (the_clock->time_left(the_clock->get_side_to_move()) == 0)
//          searcher->set_time_up(True);
//    }
    if (!searcher->is_background_search())
    {
       Display::show_search_counts(hWnd,
         searcher->get_ply(),searcher->get_numpos());
    }
}
#endif

Boolean Search::
skip_move(const Board & ABoard, const unsigned ply, const unsigned limit,
      const ExtendedMove & emove, const Boolean in_check)
{
    // Returns true if 'emove' is *not* to be evaluated.  This function
    // implements the capture and check extension heuristics.
    int limit2 = limit + extend;
    if (ply < limit2)
    return False;
    else if (ply <= limit2 + Extensions::Check_Depth && in_check)
    return False;
    else if (ply < limit2 + Extensions::Capture_Depth)
    {
    if (emove.Special() == ExtendedMove::Promotion)
    {
        return False;
    }
    else if (emove.Special() == ExtendedMove::Normal &&
           !emove.Capture().IsEmpty())
    {
        if (Scoring::check_en_prise(ABoard,emove.DestSquare(),
            emove.Capture()))
        return False;
        else if (attack_estimate( ABoard, emove ) >= 0)
            return False;
        else if (emove.PieceMoved().sliding() &&
            !ABoard.pawn_attacks(emove.DestSquare(),
         ABoard.OppositeSide()))
        {
                // Arasan's attack estimation code does not handle
                // "stacked" attackers.  To partially compensate for
                // this, we extend the search when the capturing piece
                // is "backed up" by a piece of the same color:
            int dir = ABoard.Direction(emove.StartSquare(),
                emove.DestSquare());
        if (dir)
        {
            Square sq(emove.StartSquare());
            while (!sq.OnEdge())
            {
               sq -= dir;
               Piece p = ABoard[sq];
               if (p.IsEmpty())
                   continue;
               else if (p.Color() != ABoard.Side())
                   break;
               if (p.sliding())
               {
                    Piece::PieceType ptype = p.Type();
                   if (emove.PieceMoved().Type() == Piece::Rook)
                    return ptype == Piece::Bishop;
               else if (emove.PieceMoved().Type() ==
                       Piece::Bishop)
                   return ptype == Piece::Rook;
                   else
               {
                    int abs = Util::Abs(dir);
                if (abs == 1 || abs == RankIncr)
                    return ptype == Piece::Bishop;
                else
                    return ptype == Piece::Rook;
                   }
               }
            }
        }
        }
        else
            return True;
    } else
        return True;
    }
    return True;
}

int Search::
try_move(Board & ABoard, const ExtendedMove & emove,
     const int ply, int alpha, int &beta, const int rank,
     const Boolean princip_var, const Boolean extend_search,
     Boolean &terminate, Move *best_line)
{
#ifdef TRACE
    if (ply == 0)
       cout << "window = [" << alpha << ',' << beta << ']' << endl;
    indent(ply);
    cout << "trying " << ply << ". " << emove.Image() << endl;
#endif

#ifndef NULL_MOVE
    assert(!emove.IsNull());
#endif
    // search one ply deeper, following 'emove'.  If 'extend_search'
    // is set, search two plies.

    int score;
    // allocate on the heap (to minimize stack usage):
    if (move_stack[ply] == NULL)
      move_stack[ply] = new ReversibleMove(ABoard, emove);
    else
      *(move_stack[ply]) = ReversibleMove(ABoard, emove);
    ABoard.MakeMove(*(move_stack[ply]));
    game_moves->add_move(ABoard,*(move_stack[ply]));
    if (ABoard.num_attacks(ABoard.KingPos(ABoard.OppositeSide()),
               ABoard.Side()) > 0)  // move into check
    {
#ifdef TRACE
        indent(ply);
    cout << "(illegal)" << endl;
#endif
    score = Illegal;
    }
    else
    {
    last_move[ply] = emove;
    if (princip_var || rank == 1)
    {
       if (extend_search)
       {
          extend++;
          score = -move_search(ABoard, -beta, -alpha, ply + 1,
                      princip_var,
                  terminate, best_line);
          extend--;
       }
       else
          score = -move_search(ABoard, -beta, -alpha, ply + 1,
                  princip_var,
                  terminate, best_line);
#ifdef TRACE
      indent(ply);
      cout << ply << ". " << emove.Image() << ' ';
       cout << score;
      if (princip_var)
         cout << " (pv)";
      cout << endl;
#endif
    }
    else
    {
       if (extend_search)
       {
           ++extend;
        score = -move_search(ABoard, -alpha-1, -alpha, ply + 1,
            princip_var,
               terminate, best_line);
        --extend;
       }
       else
        score = -move_search(ABoard, -alpha-1, -alpha, ply + 1,
            princip_var,
               terminate, best_line);
#ifdef TRACE
       indent(ply);
       cout << ply << ". " << emove.Image() << ' ';
        cout << score << endl;
#endif
       if (!emove.IsNull() && score > alpha && score < beta)
       {
#ifdef TRACE
          indent(ply);
          cout << "no cutoff, re-searching..." << endl;
#ifdef TRACE
    if (ply == 0)
       cout << "window = [" << -beta << ',' << -score << ']' << endl;
    indent(ply);
    cout << "trying " << ply << ". " << emove.Image() << endl;
#endif
#endif
          if (extend_search)
          {
              extend++;
              score = -move_search(ABoard, -beta, -score, ply + 1,
                  princip_var,
                  terminate, best_line);
          extend--;
          }
          else
                  score = -move_search(ABoard, -beta, -score, ply + 1,
                  princip_var,
                  terminate, best_line);
#ifdef TRACE
         indent(ply);
         cout << ply << ". " << emove.Image() << ' ';
          cout << score << endl;
#endif
       }
    }
    }
    ABoard.UndoMove(*(move_stack[ply]));
    game_moves->remove_move();
#ifdef WINDOWS
    // Yield control via PeekMessage to allow other Windows applications
    // to run when our message queue is empty.  Also, this allows
    // keyboard accelerators to be active during a background search.
    if (!accel)
        accel = App.loadAccel("AppAccel");
    HWND hwnd = (*appWin)();
    MSG msg;
    if (!terminated && PeekMessage(&msg,NULL,0,0,PM_REMOVE))
    {
      if (msg.message==WM_QUIT ||
          msg.message==WM_DESTROY ||
          (msg.message==WM_SYSCOMMAND && msg.wParam == SC_CLOSE))
      {
          // We cannot handle WM_QUIT during a search in the usual
          // way.  We need to map it into WM_CLOSE.
          terminated = True;
          // make sure our search won't be interrupted:
          KillTimer(my_hwnd,idTimer);
          PostMessage(hwnd,WM_CLOSE,0,0L);
      }
          else if (!(accel && TranslateAccelerator(hwnd, accel, &msg)))
      {
               TranslateMessage(&msg);
         DispatchMessage(&msg);
      }
    }
#else
    // Provide a simple polling method of terminating after a set time
    time_t current_time = time(NULL);
    if (get_search_type() != Fixed_Ply &&
        current_time - get_start_time() > time_target)
       set_time_up(True);
#endif
    if (terminated)
    {
        time_up = True;
    terminate = True;
    }
    const Search_Type type_of_search = get_search_type();
    if (type_of_search != Fixed_Ply &&
        type_of_search != Time_Limit)
    {
       // Allow terminating early if the pv move appears to be
       // clearly superior to all others and was in the last ply, too:
       if (!time_up && ply == 0 && rank > 1 && plies_done >= 3)
       {
#ifdef WINDOWS
       // require that we have consumed at least 1/3 of the time
       // limit:
           time_t current_time = time(NULL);
           if ((current_time - get_start_time())*3 > time_target)
       {
#endif
       if (ply0scores[0] > ply0scores[1] + 128 &&
               ply0moves[0] == best_moves[plies_done] &&
           ply0scores[0] >= best_scores[plies_done] - 32)
          time_up = True;
#ifdef WINDOWS
       }
#endif
       else if (!time_added && ply == 0 && plies_done >= 3 &&
                rank > 0)
       {
           time_t current_time = time(NULL);
               if ((current_time - get_start_time())*3 > 2*time_target)
           {
              // add a little more time to the search if the score
              // has changed a lot since the last ply.
              if (Util::Abs(ply0scores[0]-best_scores[plies_done]) > 64)
              {
                  time_added = time_target/4;
              time_up = False;
          }
           }
       }
       }
    }
    if (time_up)
    {
        terminate = True;
        if (!princip_var) // don't allow current move to be selected
             score = Illegal;
    }
    return score;
}

unsigned Search::
generate_moves(
           Board & board, Move_Generator & mg,
           const unsigned ply,
           Move * moves,
           const Boolean captures_only)
{
    int i;
    if (ply == 0 && ply0moves_generated)
    {
        // Make sure that in case of a tied score, the actually
    // chosen best move at ply n-1 is used first in this ply:
        for (i = 0; i < ply0move_count; i++)
       if (pv[0] == ply0moves[i])
       {
          ply0scores[i]++;
          break;
       }
    Move_Ordering::sort_moves(ply0moves, ply0scores, ply0move_count);
    // Because of cutoffs, we may not have exact scores for
    // moves besides the p.v.  Therefore still use the move ordering
    // code to tweak the remaining scores a bit.
    if (ply0move_count > 1)
    {
      for (i = 1; i < ply0move_count; i++)
         ply0scores[i] += Move_Ordering::score(board,ply0moves[i]);
      Move_Ordering::sort_moves(ply0moves+1, ply0scores+1, ply0move_count-1);
    }
    for (i = 0; i < ply0move_count; i++)
        moves[i] = ply0moves[i];
    return ply0move_count;
    }
    int    n = mg.Generate_Moves(moves, captures_only);

    Move_Ordering::order_moves(board, moves, n, ply, Move::NullMove());
    return n;
}

int Search::
evalu8(const Board & board)
{
    // evaluate a board position.
    num_pos++;
    int score = Scoring::material_score(board);
    score += Scoring::positional_score(board);
    if (global_options->randomize_moves())
    {
        static int fudge = Constants::PawnValue/10;
    int r = rand()/16;
#ifdef __BORLANDC__
    score += -fudge + (r*fudge)/(RAND_MAX/16);
#else
    score += -fudge + (r*fudge)/(INT_MAX/16);
#endif
    }
    return score;
}

Boolean Search::is_draw( const Board &board, int &rep_count)
{
    // check for draws due to repetition or insufficient material.

    rep_count = game_moves->rep_count(board);
    if (rep_count >= 3)
      return True;
    // check for insufficient material
    const Material &mat1 = board.getMaterial(board.Side());
    const Material &mat2 = board.getMaterial(board.OppositeSide());
    unsigned pcount1 = mat1.count(Piece::Pawn);
    unsigned pcount2 = mat2.count(Piece::Pawn);
    if (pcount1 || pcount2)
       return False;
    const int16 king_value = Piece::Value(Piece::King);
    const int16 bishop_value = Piece::Value(Piece::Bishop);
    if ((mat1.value() <= king_value + bishop_value) &&
    (mat2.value() <= king_value + bishop_value))
    {
        if (mat1.king_only() || mat2.king_only())
    // K vs K, or K vs KN, or K vs KB
       return True;
        else if (mat1.count(Piece::Knight) || mat2.count(Piece::Knight))
        {
       // KN vs KN
       return False;
    }
        else
    {
       int i = 0;
           int d1 = -1;
       int d2 = -1;
       do
       {
          Square sq(board.PiecePos(board.Side(),i));
          if (!sq.IsInvalid())
          {
             Piece::PieceType piece = board[sq].Type();
             if (piece == Piece::Bishop)
             {
                d1 = (sq.Rank(board.Side()) + sq.File()) % 2;
             }
             sq = board.PiecePos(board.OppositeSide(),i);
         if (!sq.IsInvalid())
         {
                piece = board[sq].Type();
                if (piece == Piece::Bishop)
                {
                    d2 = (sq.Rank(board.Side()) + sq.File()) % 2;
                }
                 }
          }
          i++;
           } while (i < 16);
       // drawn if same-color bishops:
       return Boolean(d1 == d2);
        }
    }
    return False;
}

int Search::
move_search(Board & ABoard, int alpha, int beta,
        const int ply, const Boolean princip_var,
        Boolean &terminate, Move *best_line)
{
    // recursive function, implements alpha/beta search.  We use
    // the PVS (principal variation search) variant of alpha/beta.

    unsigned num_try = 0;
    int score;
    struct flag_struct
    {
       int in_check;
       int mate;
       int capture_search;
       int finished;
       int forced;
    } flags;
    flags.in_check =  ABoard.CheckStatus() == Board::InCheck;
    flags.mate = flags.capture_search = flags.finished =
      flags.forced = False;
#ifdef USE_HASH
    const int initial_alpha = alpha;
#endif
    forced[ply] = False;
    int limit = max_depth;
    for (int p = ply-1; p>=0; --p)
       if (forced[p]) ++limit;
    if (ply == 0)
       rank = 0;
    int rep_count;

    if (is_draw(ABoard,rep_count))
    {
#ifdef TRACE
    cout << "draw!" << endl;
#endif
       if (ply == 0)
          state = Search::Draw;
       return -evalu8(ABoard);
    }
    else if (ply >= max_depth + Extensions::Max_Extension + extend
       || ply >= Constants::MaxPly)
    {
    return evalu8(ABoard);
    }

    Move hash_move;
#ifdef USE_HASH
    if (ply > 0 && ply <= max_depth
#ifdef NULL_MOVE
    && !null_move)
#else
    )
#endif
    {
        Position_Info *hash_entry;
    Position_Info look(ABoard,rep_count);
        hash_entry = hash_table->search(look);
    if (hash_entry)
    {
       hash_move = hash_entry->best_move();
       if (!hash_move_valid(ABoard,hash_move))
       {
          hash_entry = NULL;
          hash_move.MakeNull();
       }
    }
    if (hash_entry)
        {
        flags.forced = forced[ply] = hash_entry->forced();
        if (hash_entry->depth() >= limit-ply)
        {
        // Whether we can use the hash value or not depends on
        // the flags:
        const int value = hash_entry->value();
        Boolean valid = False;
        switch(hash_entry->type())
        {
           case Position_Info::Valid:
             valid = True;
         break;
           case Position_Info::UpperBound:
         beta = Util::Min(value,beta);
         break;
           case Position_Info::LowerBound:
         alpha = Util::Max(value,alpha);
         break;
           default:
             break;
        }
            best_line[ply] = hash_entry->best_move();
        best_line[ply+1] = Move::NullMove();
        if (valid)
        {
           return hash_entry->value();
        }
        else if (alpha > beta)
        {
           if (hash_entry->type() == Position_Info::LowerBound)
               return alpha;
           else
               return beta;
        }
        }
    }
    }
#endif

#ifdef TRACE
   if (!hash_move.IsNull())
   {
          indent(ply);
       cout << "hash move = " << hash_move.Image() << endl;
   }
#endif

    score = -Constants::BIG;
    Move *moves = moves_generated[ply];
    Move *candidate_line = candidates[ply];
    if (!candidate_line)
    {
       candidate_line = candidates[ply] = new Move[Constants::MaxPly];
    }
    int try_score;
    ExtendedMove the_last_move;
    Move best_move;

    if (ply != 0)
    the_last_move = last_move[ply - 1];

    // Most extensions do not alter the onset of the quiescence search,
    // just its termination depth.  However, forced moves do extend the
    // start of the quiesence search, to 'limit'.  We do this for two
    // reasons: it is relatively cheap, and it helps find (or avoid)
    // forced mating sequences.
    flags.capture_search = (ply >= limit && !flags.in_check);
    int cap_score = -Constants::BIG;
    Boolean extend_search = False;

    if (flags.capture_search)
    {
    // We are in the capture search and will not consider
    // all possible moves (or even all possible captures).
    // Hence, we evaluate the present position and use the more
    // optimistic of the value of the present position and the
    // best value returned by the capture search.

    // But we do not allow the side to move to "stand pat" if it
    // has a trapped or hung piece.

    int value = evalu8(ABoard);
    if ((Scoring::trapped || (Scoring::en_prise >= 1)) &&
        ply == limit /*max_depth*/)
    {
        extend_search = True;
        flags.capture_search = False;
    }
    else
    {
            cap_score = score = value;
#ifdef TRACE
            indent(ply);
        cout << "cap_score = " << cap_score << endl;
#endif
    }
    }

#ifdef NULL_MOVE
    // Try the null move
    if (!princip_var && !flags.in_check && !null_move &&
        ply <= limit - 3 &&
    ABoard.getMaterial(ABoard.Side()).value() > 2500 &&
    ABoard.getMaterial(ABoard.OppositeSide()).value() > 2500)
    {
        null_move = True;
    // search to less than full depth:
    --max_depth;
    ExtendedMove emove; // null move
        try_score = try_move(ABoard, emove, ply, alpha, beta, num_try,
                     False,
                 False,
                 terminate,
                 candidate_line );
        ++max_depth;
        null_move = False;
        if (try_score >= beta)
       score = try_score;
    }
#endif

    Boolean generated_moves = False;
    unsigned move_count;
    Move_Generator mg(ABoard, ply, the_last_move);
    if (score < beta)
    {
        if (!moves)
           moves = moves_generated[ply] = new Move[Move_Generator::MaxMoves];
        if (hash_move.IsNull())
        {
           move_count = generate_moves(ABoard, mg, ply,
                 moves,
                 Boolean(flags.capture_search));
           num_moves += move_count;
           generated_moves = True;
       flags.forced = forced[ply] =
          !flags.capture_search && move_count == 1;
        }
        else
        {
       // Delay generating the moves, use the hash move 1st.
       // If it causes cutoff, we never need to do full move generation.
           move_count = 1;
           moves[0] = hash_move;
        }
    }

    // do the principal variation first

    candidate_line[ply+1] = Move::NullMove();
    unsigned move_index = 0;
    extend_search = extend_search || flags.forced;
    while (move_index < move_count && score < beta && !flags.mate &&
           !terminate)
    {
    ExtendedMove emove(ABoard, moves[move_index++]);

    if (extend_search ||
        !skip_move(ABoard, ply, limit, emove, (Boolean)flags.in_check))
    {
        try_score = try_move(ABoard, emove, ply, alpha, beta, num_try,
                     princip_var,
                 extend_search,
                 terminate,
                 candidate_line );
        if (try_score != Illegal)
        {
            score = try_score;
        num_try++;
        if (ply == 0)
        {
            ply0moves[0] = emove;
            ply0scores[0] = score;
            rank++;
        }
        best_move = emove;
        if (score < cap_score)
            score = cap_score;
        best_line[ply] = best_move;
        if (ply == 0)
           flags.mate = score >= Constants::BIG - (int)limit - 1;
        else
           flags.mate = score >= Constants::BIG - (int)ply - 1;
        break;
        }
    }
#ifdef TRACE
    else
    {
        indent(ply);
        cout << "skipping " << emove.Image() << endl;
        }
#endif
    }

    // Principal variation done, now do the rest of the moves

    if (!generated_moves && score < beta && !flags.mate)
    {
       move_count = generate_moves(ABoard, mg, ply,
                 moves,
                 Boolean(flags.capture_search));
       num_moves += move_count;
       flags.forced = forced[ply] = !flags.capture_search && move_count == 1;
       move_index = 0;
       extend_search = extend_search || flags.forced;
    }
    while (move_index < move_count && score < beta && !flags.mate &&
           !terminate)
    {
        if (num_try > 1)
         alpha = Util::Max(alpha, score);
    ExtendedMove emove(ABoard, moves[move_index++]);
    if (((Move)emove != hash_move) && (extend_search ||
       !skip_move(ABoard, ply, limit, emove, flags.in_check)))
    {
        candidate_line[ply+1].MakeNull();
        try_score = try_move(ABoard, emove, ply,
                  alpha, beta, num_try, False,
                  extend_search, terminate,
                  candidate_line);
        if (try_score == Illegal || terminate)
        continue;
        else
        num_try++;
        if (try_score < cap_score)
        try_score = cap_score;
        if (try_score > score)   // new best move
        {
        score = try_score;
        best_move = emove;
        int j;
        for (j = ply + 1;
             j < Constants::MaxPly && !candidate_line[j].IsNull();
             ++j)
        {
             best_line[j] = candidate_line[j];
        }
        best_line[j].MakeNull();
        best_line[ply] = best_move;
        if (ply == 0)
           flags.mate = score >= Constants::BIG - (int)limit - 1;
        else
           flags.mate = score >= Constants::BIG - (int)ply - 1;
        }
        if (ply == 0)
        {
        ply0moves[rank] = (Move) emove;
        ply0scores[rank] = try_score;
        rank++;
        }
    }
    }
    flags.finished = move_index == move_count;
    Boolean Cutoff = (score >= beta);
#ifdef TRACE
    if (Cutoff)
    {
       indent(ply);
       cout << "**CUTOFF**" << endl;
    }
#endif

    if (num_try == 0 && flags.finished && !flags.capture_search)
    {
    // no moves were tried
    if (flags.in_check)
    {
        if (move_count == 0)    // mate
        {
           score = -(Constants::BIG - ply);
           if (ply == 0)
               state = Search::Checkmate;
        }
        else
        {
            // We generated some moves, and some were legal,
        // but we skipped them all.
        score = evalu8(ABoard);
        }
    }
    else if (ply < limit)    // stalemate
    {
        if (ply == 0)
           state = Search::Stalemate;
        score = -evalu8(ABoard);
    }
    }
    else if (num_try > 0)
    {
    if (Cutoff)
    {
           // If the last move caused cutoff, and was not an immediate
       // re-capture, save it as a "killer" move:
       if (ply == 0 ||
             last_move[ply].DestSquare() != last_move[ply - 1].DestSquare())
           Move_Ordering::set_killer(last_move[ply], ply);
    }
        // If there's only one legal move, don't search any more:
        if (ply == 0 && num_try == 1 && flags.finished)
           terminate = True;
    }
    if (terminated)
    {
           state = Search::Terminated;
    }
#ifdef USE_HASH
    if (ply > 0 && ply <= limit)
    {
        // store the position in the hash table, if there's room
    Position_Info::ValueType val_type;
    if (score <= initial_alpha)
    {
        val_type = Position_Info::UpperBound;
#ifdef TRACE
        cout << 'U';
#endif
        best_move.MakeNull();
    }
    else if (score >= beta)
    {
        val_type = Position_Info::LowerBound;
#ifdef TRACE
        cout << 'L';
#endif
        }
    else
    {
        val_type = Position_Info::Valid;
#ifdef TRACE
        cout << 'E';
#endif
    }
        Position_Info my_pi(ABoard, limit-ply,
       val_type, flags.forced, rep_count, score, best_move);
        Position_Info look(ABoard,rep_count);
        Position_Info *hash_entry = hash_table->search(look);
    if (hash_entry)
    {
       if (limit-ply > hash_entry->depth() ||
           (hash_entry->type() != Position_Info::Valid &&
            val_type == Position_Info::Valid))
          *hash_entry = my_pi;
    }
    else
    {
       hash_table->insert(my_pi);
    }
    }
#endif
    if (ply == 0 && flags.finished)
    {
    ply0move_count = rank;
    ply0moves_generated = True;
    }
    return score;
}

Search :: Search()
{
    last_move = new ExtendedMove[Constants::MaxPly];
    best_moves = new Move[Constants::MaxPly];
    pv = new Move[Constants::MaxPly];
    searching = False;
    plies_done = 0;
#ifdef USE_HASH
#ifdef WINDOWS
    // Size the hash table according to how much memory we have.
    // Hash table sizes should be prime.
    static unsigned sizes[8]={ 997, 1997, 3001, 4003, 4999, 6007, 6997, 8003 };
    DWORD memSize = GlobalCompact(0);
    int i;
    for (i = 0; i < 7; i++)
    if (16L*sizeof(Position_Info)*((long)sizes[i]) > memSize/8)
        break;
    hash_table = new Hash < Position_Info > (sizes[i],(unsigned long)(sizes[i])*16L);
#else
    hash_table = new Hash < Position_Info > (Constants::Hash_Size,
                     Constants::Max_Hash_Table_Entries);
#endif
#endif
}

Search::~Search()
{
    delete [] last_move;
    delete [] best_moves;
    delete [] pv;
#ifdef USE_HASH
    // free the memory only if this is the only active search:
#ifdef WINDOWS
    if (search_number == 0)
#endif
    {
       hash_table->clear(True);
    }
    delete hash_table;
#endif
}

Move Search::find_best_move(
#ifdef WINDOWS
   HWND hWnd,
#endif
   const Board & ABoard,
   const Time_Info &ti,
#ifdef WINDOWS
   const Boolean background,
#endif
   Statistics & stats,
   Move &prev_move,
   Boolean use_previous_search )
{
    searching = True;
    timeCtrl = ti;
#ifdef WINDOWS
    my_hwnd = hWnd;
    moves_in_game = game_moves->num_moves()/2; // full moves, not half-moves
    pred_moves = 60;
    if (moves_in_game > 40)
       pred_moves += (moves_in_game-40)/2;
#endif
    time_added = 0L;
    const Search_Limit limits = timeCtrl.get_search_limit();
    switch (timeCtrl.get_search_type())
    {
       case Fixed_Ply:
         break;
       case Time_Limit:
         time_target = limits.seconds;
     break;
#ifdef WINDOWS
       case Tournament:
     time_target =
       (limits.limit.minutes*60L*8L)/(limits.limit.moves*10L);
          break;
       case Game:
     unsigned long game_elapsed =
        the_clock->elapsed_time(ABoard.Side());
         time_target = (limits.limit.minutes*60L - game_elapsed)/
                (pred_moves - moves_in_game);
#else
      // Tournament & Game limits not supported under DOS
      default:
         break;
#endif
    }
    num_pos = num_moves = 0L;
#ifdef NULL_MOVE
    null_move = False;
#endif
    time_up = terminated = False;
    side_to_move = ABoard.Side();
#ifdef WINDOWS
    bkgrnd_search = background;
    assert(num_searches < MAX_SEARCHES);
    search_number = num_searches;
    searches[search_number] = this;
    ++num_searches;
#endif
    // We can use the results of a previous search only if it
    // was deep enough and if we predicted the last move.
    use_previous_search &= (stats.plies_completed >= 2) &&
       (stats.best_line[0] == prev_move);
    if (use_previous_search)
       plies_done = stats.plies_completed - 1;
    else
       plies_done = 0;
    time_t end_time;
    start_time = time(NULL);
    state = Search::Normal;
    extend = 0;
    int i;
    Boolean end_of_line = False;
    for (i = 0; i < Constants::MaxPly; i++)
    {
    move_stack[i] = NULL;
    moves_generated[i] = NULL;
    candidates[i] = NULL;
    if (use_previous_search && !end_of_line)
    {
       pv[i] = stats.best_line[i+1];
       end_of_line = pv[i].IsNull();
    }
    else
           pv[i].MakeNull();
    }
    if (use_previous_search)
    {
       for (int j = 0; j < Constants::MaxPly-1; j++)
       {
          ExtendedMove emove;
          Move_Ordering::get_killer(emove,j+1);
      Move_Ordering::set_killer(emove,j);
       }
    }
    else
    {
       Move_Ordering::clear_killer();
    }
    ply0moves_generated = False;
    ply0move_count = 0;

    Boolean terminate = False;
    unsigned ply_limit = (get_search_type() == Fixed_Ply) ? limits.max_ply :
                  Constants::MaxPly;
#ifdef WINDOWS
    // set timer every 1000 ms. (1 second).  Note: we use smart
    // callbacks (-WS), so we don't need to call MakeProcInstance.
    idTimer = SetTimer(hWnd, num_searches+SEARCH_TIMER-1,
                1000, (TIMERPROC)TimerProc);
    if (!idTimer)
    {
        MessageBox(hWnd,"Too many clocks or timers!","",
        MB_ICONEXCLAMATION | MB_OK);
        ExtendedMove null_move;
    return null_move;
    }
#endif

    int start = Util::Max(1,plies_done);
    // Searching may alter the board, either permanently (e.g. PiecePos)
    // or temporarily (during a search), so operate on a copy:
    Board board_copy = ABoard;
    for (int ply = start;
         ply <= ply_limit && !terminate && !time_up;
     ply++)
    {
        plies_done = ply - 1;
    int value;
    max_depth = display_depth = ply;
    int lo_window, hi_window;
    if (ply == start)
        value = evalu8(ABoard);
    else
        value = stats.value;
        lo_window = value - Constants::Initial_Search_Window / 2;
    hi_window = value + Constants::Initial_Search_Window / 2;
    stats.value =
      move_search(board_copy, lo_window, hi_window, 0, True,
              terminate, pv);

        if (!terminate)
        {
       if (stats.value > hi_window)
       {
#ifdef TRACE
          cout << "high cutoff, re-searching ..." << endl;
#endif
             // high cutoff, must re-search
              stats.value =
             move_search(board_copy, hi_window, Constants::BIG-1, 0, True,
                      terminate, pv);
           }
           else if (stats.value < lo_window )
       {
#ifdef TRACE
             cout << "low cutoff, re-searching ..." << endl;
#endif
           stats.value =
             move_search(board_copy, -Constants::BIG, lo_window, 0, True,
                      terminate, pv);
       }
        }

        best_moves[ply] = pv[0];
        best_scores[ply] = stats.value;
#ifdef TRACE
    cout << ply << " ply search result: " << pv[0].Image() <<
       "   value = " << stats.value << endl;
#endif
    if (stats.value <= ply - Constants::BIG /* we're checkmated */ ||
        stats.value > Constants::BIG - 100)    // mate
        break;
    }
#ifdef WINDOWS
    if (!is_background_search())
        Display::show_search_counts(hWnd,max_depth,num_pos);
#endif
    for (i = 0; i < Constants::MaxPly; i++)
    {
    delete move_stack[i];
    if (moves_generated[i])
       delete [] moves_generated[i];
    if (candidates[i])
       delete [] candidates[i];
    }
    Move ret_val = pv[0];
#ifdef WINDOWS
    KillTimer(hWnd,idTimer);
#endif

    end_time = time(NULL);
    stats.elapsed_time = end_time - start_time;
    stats.num_pos = num_pos;
    stats.num_moves = num_moves;
    stats.state = state;
    stats.max_depth = display_depth;
    if (!terminated && get_search_type() == Fixed_Ply)
       ++plies_done;
    stats.plies_completed = plies_done;
    board_copy = ABoard;
    int p;
    Move best = pv[0];
    Move_Array tmpArray;
    // Try to obtain the best line from the hash table
#ifdef USE_HASH
    for (p = 0; p < Constants::MaxPly-1; ++p)
    {
        stats.best_line[p] = best;
    ExtendedMove emove(board_copy,best);
        board_copy.MakeMove(emove);
    tmpArray.add_move(board_copy,emove);
    Position_Info look(board_copy,tmpArray.rep_count(board_copy));
        Position_Info *hash_entry = hash_table->search(look);
    if (hash_entry)
    {
        best = hash_entry->best_move();
        if (!hash_move_valid(board_copy,best))
           break;
        }
    else
        break;
    }
#endif
    stats.best_line[p].MakeNull();
    static const Boolean end_of_game[] = { False, False, False, True, True,
                               True, True, True, True };
    if (!end_of_game[(int)stats.state] &&
        global_options->can_resign() &&
        stats.value <= Constants::Contempt)
    {
        // We resign only if behind in material and if our positional
        // score is low.
        if (Scoring::positional_score(ABoard) < 40)
           stats.state = Resigns;
    }
#ifdef USE_HASH
    // This doesn't free memory, just marks it all as available again.
    hash_table->clear();
#endif
#ifdef WINDOWS
    --num_searches;
#endif
    searching = False;
    return ret_val;
}

unsigned Search::hints( const Board &ABoard,
        Move *moves,
        unsigned max_moves)
{
    searching = True;
    Search_Limit limit;
    limit.max_ply = 2;
    timeCtrl = Time_Control(Fixed_Ply,limit);

    side_to_move = ABoard.Side();
    start_time = time(NULL);
    num_pos = num_moves = 0L;
#ifdef NULL_MOVE
    null_move = False;
#endif
    state = Search::Normal;
    extend = 0;
    int i;
    move_stack[0] = NULL;
    Move_Ordering::clear_killer();
    ply0moves_generated = False;
    ply0move_count = 0;

    Boolean terminate = False;
    time_up = False;
    terminated = False;
    max_depth = display_depth = 1;
    plies_done = 0;
    for (i = 0; i < Constants::MaxPly; i++)
    {
    move_stack[i] = NULL;
    moves_generated[i] = NULL;
    candidates[i] = NULL;
        pv[i].MakeNull();
    }
#ifdef WINDOWS
    bkgrnd_search = True;
    assert(num_searches < MAX_SEARCHES);
    search_number = num_searches;
    searches[search_number] = this;
    ++num_searches;
#endif

    int value = evalu8(ABoard);
    int lo_window, hi_window;
    lo_window = value - Constants::Initial_Search_Window / 2;
    hi_window = value + Constants::Initial_Search_Window / 2;
    Board board_copy = ABoard;
    value =
      move_search(board_copy, lo_window, hi_window, 0, True,
              terminate, pv);
    if (!terminate)
    {
       if (value > hi_window)
       {
         value =
          move_search(board_copy, hi_window, Constants::BIG-1, 0, True,
                  terminate, pv);
       }
       else if (value < lo_window )
       {
        value =
         move_search(board_copy, -Constants::BIG, lo_window, 0, True,
                  terminate, pv);
       }
    }
    for (i = 0; i < Constants::MaxPly; i++)
    {
    delete move_stack[i];
    if (moves_generated[i])
       delete [] moves_generated[i];
    if (candidates[i])
       delete [] candidates[i];
    }
    // Don't clear the hash table.  Storage for the nodes and lists in the
    // table may be shared with another search in progress.  When that
    // search terminates, our memory will be cleaned up, too.
    Move_Ordering::sort_moves(ply0moves, ply0scores, ply0move_count);
    int n = Util::Min(ply0move_count,max_moves);
    for (i = 0; i < n; i++)
        moves[i] = ply0moves[i];
#ifdef WINDOWS
    --num_searches;
#endif
    searching = False;
    return n;
}